package com.niuke.linkedlist;

/**
 * 链表内指定区间反转
 *
 * @author luhd
 * @date 2023-11-17
 */
public class Bm2 {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        ListNode listNode = reverseBetween(listNode1,2,4);
    }

    /**
     * 反转链表
     *
     * @param head 链表头节点
     * @return 反转后的链表
     */
    public static ListNode reverseBetween (ListNode head, int m, int n) {
        // 1->2->3->4->5
        // 1->3->2->4->5
        // 1->4->3->2->5
        ListNode dum = new ListNode(0);
        dum.next = head;
        ListNode pre = dum;
        for (int i=1; i<m; i++) {
            pre = pre.next;
        }
        // 记录m节点
        head = pre.next;
        // 记录当前节点的后继节点
        ListNode next;
        for (int i=m; i<n; i++) {
            // next = 2
            next = head.next;
            // 1->3
            head.next = next.next;
            // 2->
            next.next = pre.next;
            pre.next = next;
        }
        return dum.next;
    }

     public static class ListNode {
       int val;
       ListNode next = null;
       public ListNode(int val) {
         this.val = val;
       }
     }
}